for _ in range(int(input())):
n = int(input())
s = input()
p1=0
p2=0
cntC=0
cntB=0
ans = float('inf')
if ('abbacca' in s) or ('accabba' in s):
ans = 7
while p1<n:
if s[p1]=='a':
p2=p1+1
break
else:
p1+=1
while p2<n:
if s[p2]=='a':
if cntB<2 and cntC<2:
ans = min(ans,p2-p1+1)
cntB=0
cntC=0
p1=p2
p2+=1
if ans==2:
break
elif s[p2]=='b':
cntB+=1
p2+=1
else:
cntC+=1
p2+=1
if ans>n:
print(-1)
else:
print(ans)#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const char nl = '\n';
const ll INF = 4000000000000000000;
const int MOD = 1000000007; // 998244353
int f(string &s, int l, int r) {
int cnt = 0;
for (int i = l; i <= r; ++i) {
if (s[i] == 'b') {
++cnt;
}
}
return max(cnt, r-l-cnt);
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i+1 < n; ++i) {
if (s[i] == 'a' && s[i+1] == 'a') {
cout << 2 << nl;
return;
}
}
for (int i = 0; i+2 < n; ++i) {
if (s[i] == 'a' && s[i+2] == 'a') {
cout << 3 << nl;
return;
}
}
for (int i = 0; i+3 < n; ++i) {
if (s[i] == 'a' && s[i+3] == 'a' && s[i+1] != s[i+2]) {
cout << 4 << nl;
return;
}
}
for (int i = 0; i + 6 < n; ++i) {
if (s[i] == 'a' && s[i+3] == 'a' && s[i+6] == 'a' && f(s, i+1, i+5) < 3) {
cout << 7 << nl;
return;
}
}
cout << -1 << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
}
/* TEMPLATE NOTES
New ideas?
Overflow error?
Array bound?
a*(b/c) != a*b/c
*/
// LEMMA: odgovor pocinje sa A.
// dokaz: Pretpostavimo da ne pocinje sa A.
// Taj string tada pocinje sa B ili sa C.
// Neka Acnt, Bcnt i Ccnt redom oznacavaju
// broj pojavljivanja A, B i C u tom odgovoru.
// Neka su l i r pocetak i kraj polozaja naseg
// odgovora u stringu. String l+1 i r je isto
// tacan jer, ako je Acnt > max(Bcnt, Ccnt),
// Onda je i Acnt vece od oba broja pojavljivanja
// B i C u string l+1 i r. Duzina odgovora koji smo
// prvobitno gledali je r-l, a duzina ovog novog validnog
// string je r-l-1. Kako je r-l-1 < r-l, dobijamo kontradikciju.
// Slicno se i dokazuje da se zavrsava sa A.1920. Build Array from Permutation | 494. Target Sum |
797. All Paths From Source to Target | 1547B - Alphabetical Strings |
1550A - Find The Array | 118B - Present from Lena |
27A - Next Test | 785. Is Graph Bipartite |
90. Subsets II | 1560A - Dislike of Threes |
36. Valid Sudoku | 557. Reverse Words in a String III |
566. Reshape the Matrix | 167. Two Sum II - Input array is sorted |
387. First Unique Character in a String | 383. Ransom Note |
242. Valid Anagram | 141. Linked List Cycle |
21. Merge Two Sorted Lists | 203. Remove Linked List Elements |
733. Flood Fill | 206. Reverse Linked List |
83. Remove Duplicates from Sorted List | 116. Populating Next Right Pointers in Each Node |
145. Binary Tree Postorder Traversal | 94. Binary Tree Inorder Traversal |
101. Symmetric Tree | 77. Combinations |
46. Permutations | 226. Invert Binary Tree |